/*
 * @lc app=leetcode.cn id=81 lang=javascript
 *
 * [81] 搜索旋转排序数组 II
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {boolean}
 */
var search = function (nums, target) {
  const size = nums.length;
  if (size === 0) return false;
  if (size === 1) return target === nums[0];

  const binarySearch = (nums, left, right, target) => {
    while (left < right) {
      let mid = left + ((right - left) >> 1);
      if (nums[mid] >= target) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return nums[left] === target ? left : -1;
  };
  let left = 0;
  let right = size - 1;

  // 恢复二段性
  while (left < right && nums[0] === nums[right]) right--;
  // 查找旋转点
  while (left < right) {
    let mid = (right + left + 1) >> 1;
    if (nums[0] <= nums[mid]) {
      left = mid;
    } else {
      right = mid - 1;
    }
  }
  let idx = size - 1;
  //[0,idx]和[idx+1,size-1]分成2个有序区间
  if (nums[right] >= nums[0] && right < idx) idx = right;

  // 左区间
  let result = binarySearch(nums, 0, idx, target);
  if (result !== -1) return true;
  // 右区间
  result = binarySearch(nums, idx + 1, size - 1, target);
  return result !== -1;
};
// @lc code=end
